#ifndef HASH_TABLE_H
#define HASH_TABLE_H

#include <stdint.h>
#include <cstring>
#include "SharedArray.h"
#include "KeyValue.h"
#include "config.h"
#include "hash.h"

// Hash table with both key and value being sequence of bytes.
class HashTable {
	public:
		HashTable(int keySize, int valueSize, const char* defaultValue):
				_keySize(keySize),
				_valueSize(valueSize),
				_htable(new Node*[INITIAL_HTABLE_SIZE]),
   				_htableSize(INITIAL_HTABLE_SIZE),
				_size(0) {
			_defaultValue = new char[_valueSize];
			memcpy(_defaultValue, defaultValue, _valueSize);

			for (int i = 0; i < INITIAL_HTABLE_SIZE; ++i)
				_htable[i] = 0;
		}

		~HashTable() {
			delete[] _defaultValue;

			for (int i = 0; i < _htableSize; ++i) {
				Node* node = _htable[i];

				while (node != 0) {
					delete[] node->key;
					delete[] node->value;

					Node* deletedNode = node;
					node = node->next;
					delete deletedNode;
				}
			}

			delete[] _htable;
		}

		// Takes concaternated keys and list of corresponding hashes.
		// Does not take ownership of arguments.
		// Returns corresponding to keys values (and freshly created default values in case
		// of key not being in hash table).
		SharedArray<char*> get(const char* keys, const hash_t* hashes, int count) {
			SharedArray<char*> result(count);

			for (int i = 0; i < count; ++i) {
				int index = hashes[i] % _htableSize;
				Node* node = _htable[index];

				const char* key = keys + (i * _keySize);

				while (node != 0) {
					if (hashes[i] == node->hash && keysEqual(node->key, key))
						break;

					node = node->next;
				}

				if (node == 0) {
					node = new Node;
					node->hash = hashes[i];
					node->key = new char[_keySize];
					memcpy(node->key, key, _keySize);
					node->value = new char[_valueSize];
					memcpy(node->value, _defaultValue, _valueSize);
					node->next = _htable[index];

					_htable[index] = node;
					++_size;
				}
				
				assert(keysEqual(node->key, key));

				result[i] = node->value;
			}

			optimizeSize();

			return result;
		}

		// Returns all key-value pairs from table.
		SharedArray<KeyValue> getEverything() {
			SharedArray<KeyValue> everything(_size);
			int count = 0;

			for (int i = 0; i < _htableSize; ++i) {
				Node* node = _htable[i];

				while (node != 0) {
					everything[count].key = node->key;
					everything[count].value = node->value;
					++count;

					node = node->next;
				}
			}

			return everything;
		}

	private:
		void optimizeSize() {
			if (_htableSize == MAX_HTABLE_SIZE || _htableSize >= HTABLE_OPTIMAL_SIZE_FACTOR * _size)
				return;

			int htableSize = HTABLE_NEW_SIZE_FACTOR * _size;
			if (htableSize > MAX_HTABLE_SIZE)
				htableSize = MAX_HTABLE_SIZE;

			Node** htable = new Node*[htableSize];
			for (int i = 0; i < htableSize; ++i)
				htable[i] = 0;

			for (int i = 0; i < _htableSize; ++i) {
				Node* node = _htable[i];

				while (node != 0) {
					Node* nextNode = node->next;

					int index = node->hash % htableSize;
					node->next = htable[index];
					htable[index] = node;

					node = nextNode;
				}
			}

			delete[] _htable;
			_htable = htable;
			_htableSize = htableSize;
		}

		bool keysEqual(const char* key1, const char* key2) {
			for (int i = 0; i < _keySize; ++i) {
				if (key1[i] != key2[i])
					return false;
			}

			return true;
		}

		struct Node {
			Node* next;
			char* key;
			char* value;
			hash_t hash;
		};

		const int _keySize;
		const int _valueSize;
		char* _defaultValue;
		Node** _htable;
		int _htableSize;
		int _size;
};

#endif
